You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example 1:
Input: nums = [5,2,6,1] Output: [2,1,1,0] Explanation: To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element.
Example 2:
Input: nums = [-1] Output: [0]
Example 3:
Input: nums = [-1,-1] Output: [0,0]
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 104
Average Rating: 4.67 (24 votes)
Solution
Overview
The problem is straightforward. For each num in nums, we need to obtain the number of smaller elements after num.
A straightforward approach is to use brute force with two for-loops. The first loop iterates over all num in nums, and the second loop iterates over all elements after num. However, this approach costs O(N2) and yields Time Limit Exceed, given that N is the length of nums.
Luckily, there are two helpful data structures: segment tree and binary indexed tree, which are able to do the range query in logarithmic time.
Also, a solution based on Merge Sort is available.
Below, we will discuss each of the three approaches: Segment Tree, Binary Indexed Tree, and Merge Sort.
After you finish, you can practice by solving some similar questions:
Approach 1: Segment Tree
Intuition
Prerequisite: segment tree
If you are not familiar with segment trees, you should check out our Recursive Approach to segment trees tutorial before continuing.
Also, here are some relevant applications for segment trees that you can practice on:
For a full list, check out the segment tree Tag.
For a particular element in nums, located at index i, we want to count how many of the numbers on the right side of index i are smaller than nums[i]. Notice that the value of the smaller numbers must be in the range (−∞,nums[i]−1].
Hence, if we can find the count of each number in the range (−∞,nums[i]−1] on the right side of index i, then the answer will be the sum of those counts.
Therefore, for each index i, we need a query to find the sum of those counts. Recall that the segment tree and the binary indexed tree are two data structures that are generally helpful when solving range query problems.
Since we need counts of values, we can use an approach similar to bucket sort, where we have buckets of values and buckets[value] stores the count of value. For each value, we increment buckets[value] by 1. With this approach, the number of elements smaller than nums[i] is the range sum of (−∞,num−1] in buckets.
With the help of a segment tree or binary indexed tree, we can perform the range sum query in logarithmic time.
With the given constraint -10^4 <= nums[i] <= 10^4, we can initialize buckets from -10^4 to 10^4.
Wait, there is a problem: Usually, we store buckets in an array, so the indices of buckets are non-negative. However, here we need to store some negative values. How can we resolve this problem?
There are two solutions:
- Use a map rather than an array.
- Shift all numbers to non-negative.
Both solutions work, and here we have chosen the second one since it is easier to implement. Interested readers are welcome to try the first one on their own.
To shift all numbers to non-negative, we simply add a constant. Here we chose the constant offset = 10^4 and increase each number by offset:
nums[i] = nums[i] + offset
The smallest number -10^4 becomes 0 under this shift.
Note that while querying a particular index, we only need to consider elements that are on the right side of the index. Therefore we need to make sure that when we query an index, say i, only elements from index i+1 to the end of the array are present in the buckets.
To achieve this, we need to traverse nums from right to left, while performing range sum queries and updating the counts.
Similarly, with the help of a segment tree or binary indexed tree, we can perform the updates in logarithmic time.
(For convenience, the offset is not included in the above picture.)
Algorithm
-
Implement the segment tree. Since the tree is initialized with all zeros, only
updateandqueryneed to be implemented. Setoffset = 10^4. -
Iterate over each
numinnumsin reverse. For eachnum:- Shift
numtonum + offset. - Query the number of elements in the segment tree smaller than
num. - Update the count of
numin the segment tree.
- Shift
-
Return the result.
Implementation
Complexity Analysis
Let N be the length of nums and M be the difference between the maximum and minimum values in nums.
Note that for convenience, we fix M=2∗104 in the above implementations.
-
Time Complexity: O(Nlog(M)).
We need to iterate overnums. For each element, we spend O(log(M)) to find the number of smaller elements after it, and spend O(log(M)) time to update the counts. In total, we need O(N⋅log(M))=O(Nlog(M)) time. -
Space Complexity: O(M), since we need, at most, an array of size 2M+2 to store the segment tree.
We need at most M+1 buckets, where the extra 1 is for the value 0. For the segment tree, we need twice the number of buckets, which is (M+1)×2=2M+2.
Approach 2: Binary Indexed Tree (Fenwick Tree)
Intuition
Prerequisite: binary indexed tree
If you are not familiar with binary indexed tree (BIT), you should check relevant tutorials, such as Range Sum Query 2D - Mutable before continuing.
Also, here are some relevant applications for binary indexed trees that you can practice on:
(Yes, many problems which can be solved by segment tree can also be solved by binary indexed tree.)
For a full list, you can check the binary indexed tree Tag.
Binary indexed tree is similar to segment tree. It allows us to perform a prefix query, such as prefix sum, in log time. Can we transform this problem into a prefix sum problem?
Yes, using the same tricks that we used in approach 1, buckets and shift, we can transform the number of smaller elements into a prefix sum for the range [0,num+offset−1], where offset=104.
Similarly, when querying, we need to traverse nums from right to left in order to ensure that only the elements to the right are in the buckets.
Algorithm
-
Implement the binary indexed tree. Since the tree is initialized with all zeros, only
updateandqueryneed to be implemented. Setoffset = 10^4. -
Iterate over each
numinnumsin reverse. For eachnum:- Shift
numtonum + offset. - Query the number of elements in the BIT that are smaller than
num. - Update the count of
numin the BIT.
- Shift
-
Return the result.
Implementation
Complexity Analysis
Let N be the length of nums and M be the difference between the maximum and minimum values in nums.
Note that for convenience, we fix M=2∗104 in the above implementations.
-
Time Complexity: O(Nlog(M)).
We need to iterate overnums. For each element, we spend O(log(M)) to find the number of smaller elements after it, and spend O(log(M)) time to update the counts. In total, we need O(N⋅log(M))=O(Nlog(M)) time. -
Space Complexity: O(M), since we need, at most, an array of size M+2 to store the BIT.
We need at most M+1 buckets, where the extra 1 is for the value 0. The BIT requires an extra dummy node, so the size is (M+1)+1=M+2.
Approach 3: Merge Sort
Intuition
Prerequisite: Merge Sort
If you are not familiar with Merge Sort, you should check relevant tutorials before continuing.
Also, here is a basic application of Merge Sort that you can practice on:
To apply merge sort, one key observation is that:
The smaller elements on the right of a number will jump from its right to its left during the sorting process.
If we can record the numbers of those elements during sorting, then the problem is solved.
Can we modify the merge sort a little to meet our needs?
Consider when merging two sorted list
Yes! When we select an element i on the left array, we know that elements selected previously from the right array jump from i's right to i's left.
By adding the counts of those elements in every merge step, we get the total number of elements that jumped from i's right to i's left.
Algorithm
-
Implement a merge sort function.
- For each element
i, the function records the number of elements jumping fromi's right toi's left during the merge sort.
- For each element
-
Merge sort
nums, store the number of elements jumping from right to left inresult.- Alternatively, one can sort the indices with corresponding values in
nums. That is to say, we are going to sort list[0, 1, ..., n-1]according to the comparatornums[i]. This helps to track the indices and updateresult. You can find additional details in the implementations below.
- Alternatively, one can sort the indices with corresponding values in
-
Return
result.
Implementation
Complexity Analysis
Let N be the length of nums.
-
Time Complexity: O(Nlog(N)). We need to perform a merge sort which takes O(Nlog(N)) time. All other operations take at most O(N) time.
-
Space Complexity: O(N), since we need a constant number of arrays of size O(N).
June 4, 2021 7:52 AM
Dam... this one is hard
Last Edit: June 5, 2021 12:13 PM
This is definately one of the best well organized solutions and the sample code is clean and readable.
can we use a stack to find the smaller element on the right
I was able to do this by iterating backwards through the array and adding each element to a new sorted array by performing a binary search to find the position to insert at and then also filling in an array in reverse with the positions returned by binary search (with a little bit of extra manipulation to see if greater vs less than current element). Complexity should be O(N log(N)). It's maybe kind of similar to the merge sort strategy but I think it's different enough to be considered a separate solution. Here it is in TypeScript:
function countSmaller(nums: number[]): number[] {
const sortedElements = [];
const smallerElements = [];
for (let i = nums.length - 1; i >= 0; i--) {
let position = binarySearch(nums[i], sortedElements);
if (sortedElements[position] >= nums[i] || sortedElements.length === 0) {
sortedElements.splice(position, 0, nums[i]);
} else {
position += 1;
sortedElements.splice(position, 0, nums[i]);
}
smallerElements.unshift(position);
}
return smallerElements;
};
const binarySearch = (value: number, nums: number[]): number => {
if (nums.length === 0) return 0;
let left = 0;
let right = nums.length - 1;
let mid = left + Math.floor((right - left) / 2);
while (left !== right) {
if (value > nums[mid]) {
// go right
left = Math.min(mid + 1, right);
} else if (value < nums[mid]) {
// go left
right = Math.max(mid - 1, left);
} else {
// sorta go left
right = mid;
}
mid = left + Math.floor((right - left) / 2);
}
return left;
};
One more approach could be to maintain a self-balancing BST (AVL tree) with subtree sum. We can use this to add elements from right to left and find number of elements that are smaller than current number.
May 22, 2021 9:48 PM
Is tree size being 2size of array safe for the segment tree ?
I thought we need 4size to represent the segment tree.
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 05/30/2021 09:05 | Accepted | 1060 ms | 83.5 MB | cpp |
| 05/27/2021 08:35 | Accepted | 628 ms | 83.5 MB | cpp |
| 06/10/2020 19:33 | Wrong Answer | N/A | N/A | cpp |
| 06/10/2020 19:31 | Runtime Error | N/A | N/A | cpp |
xxxxxxxxxx};class Solution {public: vector<int> sol; void merge(vector<pair<int,int>> &a, int start, int mid, int end){ int i = start, j = mid+1; while(i<=mid && j<=end) { if(a[i].first <= a[j].first) { sol[a[i].second] += (j-mid-1); i++; } else j++; } while(i<=mid) { sol[a[i].second] += (j-mid-1); i++; } sort(a.begin()+start,a.begin()+end+1); } void mergesort(vector<pair<int,int>> &a, int start, int end){ if(start>=end) return; int mid = start + (end-start)/2; mergesort(a, start, mid); mergesort(a, mid+1, end); merge(a, start, mid, end); } vector<int> countSmaller(vector<int>& nums) { int n = nums.size(); sol.resize(n,0); vector<pair<int,int>> idx; for(int i=0;i<n;i++) idx.push_back({nums[i],i}); mergesort(idx, 0, n-1); return sol; }